home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / wtek0693.zip / OOPALLEY.ZIP / SET.CPP < prev    next >
C/C++ Source or Header  |  1993-04-27  |  7KB  |  281 lines
  1. #include "set.h"
  2.  
  3. #define THIS    Set
  4. #define BASE    Collection
  5. DEFINE_CLASS(Set,Collection);
  6.  
  7. unsigned Set::setCapacity(unsigned int size)
  8. /*
  9.     Establish the Set capacity.  Round size up to the next highest
  10.     power of two, if necessary.
  11. */
  12. {
  13.     if (size==0)
  14.         DTerror("Negative or zero object allocation size requested: ",className());
  15.     count = 0;
  16.     nbits = 0;
  17.     for (register unsigned s=size; s!=0; s>>=1, nbits++);
  18.     if (size == 1<<(nbits-1)) --nbits;
  19.     size = 1<<nbits;
  20.     mask = size-1;
  21.     return size*CLTN_EXPANSION_FACTOR;      // return hash table capacity 
  22. }
  23.  
  24. Set::Set(unsigned size) : contents(setCapacity(size)) {}
  25.  
  26. Set::Set(const Set& s) : contents(s.contents)
  27. {
  28.     count = s.count;
  29.     mask = s.mask;
  30.     nbits = s.nbits;
  31. }
  32.  
  33. void Set::operator=(const Set& s)
  34. {
  35.     count = s.count;
  36.     mask = s.mask;
  37.     nbits = s.nbits;
  38.     contents = s.contents;
  39. }
  40.     
  41. int Set::h(unsigned long K) const
  42. /*
  43. multiplicative hash function
  44.  
  45. Enter:
  46.     K = key to be hashed
  47.     
  48. Returns:
  49.     hash table index
  50.     
  51. Knuth Vol. 3, Section 6.4, pp. 508-512
  52. */
  53. {
  54.     const unsigned long Aw = 2654435769L;   
  55. //  const unsigned long Aw = 40503;     use for 16 bit machines? 
  56.     return ((Aw*K)>>((8*sizeof(unsigned))-nbits)) & mask;
  57. }
  58.  
  59. int Set::findIndexOf(const Object& ob) const
  60. /*
  61. Search this set for the specified object
  62.  
  63. Enter:
  64.     ob = pointer to object to search for
  65.  
  66. Returns:
  67.     index of object if found or of nil slot if not found
  68.     
  69. Algorithm L, Knuth Vol. 3, p. 519
  70. */
  71. {
  72.     register int i;
  73.     for (i = h(ob.hash()); contents[i]!=nil; i = (i-1)&mask) {
  74.         if (contents[i]->isEqual(ob)) return i;
  75.     }
  76.     return i;
  77. }
  78.  
  79. void Set::reSize(unsigned newSize)
  80. /*
  81.     Change the capacity of this Set to newSize.
  82. */
  83. {
  84.     if (newSize <= size()) return;
  85.     ArrayOb oldcontents = asArrayOb();
  86.     *this = Set(newSize);
  87.     addAll(oldcontents);
  88. }
  89.  
  90. Object* Set::add(const Object& ob)
  91. /*
  92.     Add an object to this Set, making the Set larger if it
  93.     becomes half full.
  94. */
  95. {
  96.     register int i = findIndexOf(ob);
  97.     if (contents[i]==nil) {     // add new object to set 
  98.         contents[i] = (Object*)&ob;
  99.         if (++count*CLTN_EXPANSION_FACTOR > capacity()) reSize(count*CLTN_EXPANSION_FACTOR);
  100.         return (Object*)&ob;     // successful add
  101.     }
  102.     else return contents[i];    // object already in set 
  103. }
  104.  
  105. Collection& Set::addContentsTo(Collection& cltn) const
  106. /*
  107.     Add all of the objects in the specified Collection to
  108.     this Set.
  109. */
  110. {
  111.     DO(*this,Object*,o) cltn.add(*o); DONE
  112.     return cltn;
  113. }
  114.  
  115. #pragma warn -rvl   // Turn of Warning: Function should return a value
  116. Object* Set::remove(const Object& ob)
  117. /*
  118. remove object from set
  119.  
  120. Enter:
  121.     ob = reference to object to be removed
  122.  
  123. Returns:
  124.     pointer to removed object
  125.  
  126. Algorithm R, Knuth Vol. 3 p. 527
  127. */
  128. {
  129.     register int i = findIndexOf(ob);
  130.     Object* rob = contents[i];
  131.     //if (rob==nil) DTerror("OOPS_REMOVEERR,DEFAULT,this,className(),ob.className(),&ob",className());
  132.     if (rob==nil) 
  133.     {   
  134.         // DTerror aborts, return statement not executed
  135.         DTerror("Tried to remove object not in collection: ",className());
  136.         // return (Object*)NULL;                       // avoids Warning message
  137.     } else {
  138.         register int j,r;
  139.         while (YES) {
  140.             contents[j=i] = (Object*)nil;
  141.             do {
  142.                 i = (i-1)&mask;
  143.                 if (contents[i]==nil) {
  144.                     count--;
  145.                     return rob;
  146.                 }
  147.                 r = h(contents[i]->hash());
  148.             } while ((i<=r&&r<j) || (r<j&&j<i) || (j<i&&i<=r));
  149.             contents[j] = contents[i];
  150.         }
  151.     }
  152. }
  153. #pragma warn .rvl
  154.  
  155. bool Set::operator==(const Set& s) const
  156. /*
  157.     Return YES if the specified Set equals this Set.
  158. */
  159. {
  160.     if (count!=s.count) return NO;
  161.     for (register int i=0; i<capacity(); i++) {
  162.         if (contents[i]!=nil && !s.includes(*contents[i])) return NO;
  163.     }
  164.     return YES;
  165. }
  166.  
  167. Set Set::operator-(const Set& s) const
  168. /*
  169.     Returns a Set of all of the objects that are contained in this
  170.     Set but not in the specified Set.
  171. */
  172. {
  173.     Set diff = *this;
  174.     for (register int i=0; i<capacity(); i++) {
  175.         if (contents[i]!=nil && s.includes(*contents[i])) diff.remove(*contents[i]);
  176.     }
  177.     return diff;
  178. }
  179.  
  180. Set Set::operator&(const Set& s) const
  181. /*
  182.     Returns a Set of all objects that are in both this Set and
  183.     the specified Set.
  184. */
  185. {
  186.     Set intersection = *this;
  187.     for (register int i=0; i<capacity(); i++) {
  188.         if (contents[i]!=nil && !s.includes(*contents[i])) intersection.remove(*contents[i]);
  189.     }
  190.     return intersection;
  191. }
  192.  
  193. Set Set::operator|(const Set& s) const
  194. /*
  195.     Returns a Set of all objects that are in either this Set
  196.     or the specified Set.
  197. */
  198. {
  199.     Set u = *this;
  200.     u.addAll(s);
  201.     return u;
  202. }
  203.  
  204. Object*& Set::at(int i) const { return contents[i]; }
  205.  
  206. bool Set::isEqual(const Object& p) const
  207. /*
  208.     Returns YES if this Set equals the specified object.
  209. */
  210. {
  211.     return p.isSpecies(class_Set) && *this==*(Set*)&p;
  212. }
  213.  
  214. const Class* Set::species() const { return &class_Set; }
  215.  
  216. void Set::deepenShallowCopy()
  217. {
  218.     BASE::deepenShallowCopy();
  219.     contents.deepenShallowCopy();
  220. }
  221.  
  222. Object* Set::doNext(Iterator& pos) const
  223. {
  224.     Object* ob;
  225.     while (pos.index < capacity()) {
  226.         if ((ob = contents[pos.index++]) != nil) return ob;
  227.     }
  228.     return 0;
  229. }
  230.  
  231. unsigned Set::capacity() const
  232. {
  233.     return contents.capacity()/CLTN_EXPANSION_FACTOR;
  234. }
  235.  
  236. unsigned Set::hash() const
  237. {
  238.     unsigned h = 0;
  239.     DO(*this,Object*,o) h ^= o->hash(); DONE
  240.     return h;
  241. }
  242.  
  243. unsigned Set::occurrencesOf(const Object& ob) const
  244. /*
  245.     Return the number of occurences of thw specified object
  246.     in this Set (either 0 or 1).
  247. */
  248. {
  249.     if (contents[findIndexOf(ob)]!=nil) return 1;
  250.     else return 0;
  251. }
  252.  
  253. Object* Set::findObjectWithKey(const Object& ob) const
  254. {
  255.     return contents[findIndexOf(ob)];
  256. }
  257.  
  258. void Set::printOn(ostream& strm) const
  259. {
  260.     unsigned n=0;
  261.     strm << className() << "[\n";
  262.     DO(*this,Object*,o)
  263.         if (n>0) strm << "\n";
  264.         o->printOn(strm);
  265.         n++;
  266.     DONE
  267.     strm << "]\n";
  268. }
  269.  
  270. unsigned Set::size() const        { return count; }
  271.  
  272. Set Collection::asSet() const
  273. /*
  274.     Convert this Collection to a Set.
  275. */
  276. {
  277.     Set cltn(MAX(size(),CLTN_DEFAULT_CAPACITY));
  278.     addContentsTo(cltn);
  279.     return cltn;
  280. }
  281.